package com.mdnote.practice.greedy;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/22
 * @description m763. 划分字母区间
 */
public class LeetCode763 {

    public List<Integer> partitionLabels(String S) {
        if (S.length() == 0) {
            return new ArrayList<>();
        }
        int[] alphabet = new int[26];
        for (int i = 0; i < S.length(); i++) {
            alphabet[S.charAt(i) - 'a'] = i;
        }
        List<Integer> resList = new ArrayList<Integer>();

        _partitionLabels(0, 0, S, resList, alphabet);
        return resList;
    }


    private void _partitionLabels(int start, int end, String s, List<Integer> resList, int[] alphabet) {

        // Terminator
        if (end == s.length()) {

            return;
        }
        // Process
        // find end
        int i = start, j = start;
        while (i <= j && i < s.length() ) {
            int position = lastIndex(alphabet, s.charAt(i));
            if (i != position && position > j) {
                j = position;
            }
            i++;
        }
        resList.add(i - start);
        // Drill down
        _partitionLabels(i, i, s, resList, alphabet);
        // Restore
    }

    private int lastIndex(int[] arr, char c) {
        return arr[c - 'a'];
    }


    private List<Integer> greedy(String s) {

        int[] lastIndex = new int[26];

        for (int i = 0; i < s.length(); i++) {
            lastIndex[s.charAt(i) - 'a'] = i;
        }

        List<Integer> resList = new ArrayList<>();

        int start = 0, end  = 0;
        for (int i = 0; i < s.length(); i++) {
            end  = Math.max(end, lastIndex[s.charAt(i)]);
            // 此时如果end == i， 说明后面已经没有重复的元素
            if (end == i) {
                resList.add(end - start + 1);
                start = end + 1;
            }
        }
        return resList;
    }
}
